/*
Date:20210903 12:14AM
key:重做题，关键在于维护一个有序序列，和新有序元素不停地和后面的元素做交换，这样就不需要标记数组，但是输出结果将是无序。
*/
class Solution {
public:
void Dfs(vector<int>& nums,int first,vector<vector<int>>&per)
{
    if(first==nums.size())
    {
        per.push_back(nums);
        return;
    }
    
    for(int i=first;i<nums.size();i++)
    {
        //if(s.count(nums[i])==0)
        {//第first个有序，first后面的与当前交换
            swap(nums[first],nums[i]);
            Dfs(nums,first+1,per);
            swap(nums[first],nums[i]);
        }
    }
    
}
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int>v;
        
        set<int>s;
        vector<vector<int>>per;
        Dfs(nums,0,per);
        
        return per;
    }
};